Finality Gadget
Ebb-and-Flow Protocols: A Resolution of the Availability-Finality Dilemma
Joachim Neu and Ertem Nusret Tas and David Tse (Stanford)
Simulation in Julia GitHub
Hierarchical Finality Gadget, @ethresear.ch, 2020.01, nrryuya
Casper FFG
Adopted in Ethereum 2.0
See Casper FFG
GRANDPA
Adopted in Polkadot
Papers (GitHub)
Overview: Medium, Video, Wiki/consensus, NEAR Whiteboard series
Implementation
Block production mechanism is BABE inspired by Ouroboros Praos
See Ouroboros
Comparison to FFG
in GRANDPA, different voters can cast votes simultaneously for blocks at different heights
GRANDPA only depends on finalized blocks to affect the fork-choice rule of the underlying block production mechanism
Nightshade Finality Gadget
Adopted in Near Protocol
Doomslug: + Nightshade Finality Gadget (NFG)
Doomslug: block confirmation with single round of communication, and a finality gadget with guaranteed liveness
Video
Previous version of NFG: Fast Finality and Resilience to Long Range Attacks with Proof of Space-Time and Casper-like Finality Gadget 2019.10
Afgjort
Afgjort: A Partially Synchronous Finality Layer for Blockchains
Bernardo Magri (Aarhus University), Christian Matt (Concordium), Jesper Buus Nielsen and Daniel Tschudi
About Concordium Slide, Video
SCN'20
Define desired properties for finality layer called (∆, k)-finality: Chain-forming, Agreement, Δ-Updated, k-support
Partial synchrony (unknown$ \Delta_\mathrm{net}) with gossip network
Perform Weak Multi-Valued Byzantine Agreement (, which is reduced to a binary, randomized & graded Byzantine agreement) on blocks to finalize
Dynamically adjust the depth (to keep up with the chain growth) and the number of the prefix
Assume 1. bounded dishonest chain growth or 2. allow dishonest chain to be finalized and make a rollback (i.e. 1-support)
Non-incentive-wise argument on long-range attack (4.1)
UC proof sketch (Section 4.2)